首页 > 试题广场 >

密码锁

[编程题]密码锁

热度指数：3758 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串（2=<N<=13），该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。

输入描述:

第一行输入N，第二行输入N个数字，只包含0，1，2

输出描述:

输出字符串要移几位才能解开密码，如果无论移位多少次都解不开密码，输出-1

示例1

输入

输出

1
1

算法知识视频讲解

Python 3

牛客309552890号

from collections import deque
from copy import deepcopy


def switcher(s,level):
    ss = []
    for i in s:
        ss.append(i)
    
    result = []
    for i in range(len(ss)-1):
        new_one = deepcopy(ss)
        new_one[i+1] = ss[i]
        new_one[i] = ss[i+1]
        
        new_s = ''.join(new_one)
        result.append( (new_s,level+1) )
    return result
while True:
    try:
        m = input()
        orig_s = input().strip()
        if '2012' in orig_s:
            print(0)
            continue
        q = deque([])
        used = set()
        q.extend(switcher(orig_s,0))
        used.add(orig_s)
        #print(orig_s)
        while len(q) != 0:
            #print(q)
            one,level = q.popleft()
            if one in used:
                continue
            else:
                if '2012' in one:
                    print(level)
                    break
                else:
                    q.extend(switcher(one,level))
                    used.add(one)
        else:
            print(-1)
    except:
        break

发表于 2021-09-06 23:28:13 回复(0)